Browsing by Subject "Selfish routing"

Now showing items 1-12 of 12

    • Conference Object  

      Computing Nash equilibria for scheduling on restricted parallel links 

      Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard (2004)
      We consider the problem of routing n users on m parallel links, under the restriction that each user may only be routed on a link from a certain set of allowed links for the user. Thus, the problem is equivalent to the ...
    • Article  

      Facets of the fully mixed Nash equilibrium conjecture 

      Feldmann, R.; Mavronicolas, Marios; Pieris, Andreas (2010)
      In this work, we continue the study of the many facets of the Fully Mixed Nash Equilibrium Conjecture, henceforth abbreviated as the FMNE Conjecture, in selfish routing for the special case of n identical users over two ...
    • Article  

      A new model for selfish routing 

      Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; Rode, M. (2008)
      In this work, we introduce and study a new, potentially rich model for selfish routing over non-cooperative networks, as an interesting hybridization of the two prevailing such models, namely the KPmodel [E. Koutsoupias, ...
    • Article  

      A new model for selfish routing 

      Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; Rode, M. (2004)
      In this work, we introduce and study a new model for selfish routing over non-cooperative networks that combines features from the two such best studied models, namely the KP model and the Wardrop model in an interesting ...
    • Article  

      The price of anarchy for polynomial social cost 

      Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard (2006)
      In this work, we consider an interesting variant of the well studied KP model for selfish routing on parallel links, which reflects some influence from the much older Wardrop model [J.G. Wardrop, Some theoretical aspects ...
    • Article  

      The price of anarchy for polynomial social cost 

      Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard (2004)
      In this work, we consider an interesting variant of the well-studied KP model [18] for selfish routing that reflects some influence from the much older Wardrop model [31]. In the new model, user traffics are still unsplittable, ...
    • Article  

      The price of selfish routing 

      Mavronicolas, Marios; Spirakis, Paul G. (2007)
      We study the problem of routing traffic through a congested network. We focus on the simplest case of a network consisting of m parallel links. We assume a collection of n network users
    • Article  

      Selfish routing in the presence of network uncertainty 

      Georgiou, Chryssis; Pavlides, Theophanis; Philippou, Anna (2009)
      We study the problem of selfish routing in the presence of incomplete network information. Our model consists of a number of users who wish to route their traffic on a network of m parallel links with the objective of ...
    • Article  

      Structure and complexity of extreme Nash equilibria 

      Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; Spirakis, Paul G. (2005)
      We study extreme Nash equilibria in the context of a selfish routing game. Specifically, we assume a collection of n users, each employing a mixed strategy, which is a probability distribution over m parallel identical ...
    • Article  

      The structure and complexity of Nash equilibria for a selfish routing game 

      Fotakis, Dimitris A.; Kontogiannis, Spyros C.; Koutsoupias, Elias; Mavronicolas, Marios; Spirakis, Paul G. (2009)
      In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models selfish routing over a network consisting of m parallel links. We assume a collection ...
    • Article  

      The structure and complexity of Nash equilibria for a selfish routing game 

      Fotakis, Dimitris A.; Kontogiannis, Spyros C.; Koutsoupias, Elias; Mavronicolas, Marios; Spirakis, Paul G. (2002)
      In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models selfish routing over a network consisting of m parallel links. We assume a collection ...
    • Article  

      Which is the worst-case Nash equilibrium? 

      Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; Rode, M.; Spirakis, Paul G.; Vrto, I. (2003)
      A Nash equilibrium of a routing network represents a stable state of the network where no user finds it beneficial to unilaterally deviate from its routing strategy. In this work, we investigate the structure of such ...